package Tree.Recursive;

import Utils.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 对称二叉树: 给定一个二叉树，检查它是否是镜像对称的。
 * Lettcode 101: https://leetcode-cn.com/problems/symmetric-tree/
 */
public class isSymmetric {
    /**
     * 方法一：递归 当root不为空时
     * 基线条件为：
     *         if (leftroot == null && rightroot == null) {
     *             return true;
     *         }
     *         if (rightroot == null || leftroot == null || rightroot.val != leftroot.val) {
     *             return false;
     *         }
     * 递归条件为：
     *         left.left == right.right && left.right == right.left
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isValid(root.left, root.right);
    }

    private boolean isValid(TreeNode leftroot, TreeNode rightroot) {
        if (leftroot == null && rightroot == null) {
            return true;
        }
        if (rightroot == null || leftroot == null || rightroot.val != leftroot.val) {
            return false;
        }
        return isValid(leftroot.left, rightroot.right) && isValid(leftroot.right, rightroot.left);
    }

    /**
     * 方法二：迭代，利用树的广度优先搜索进行迭代
     * @param root
     * @return
     */
    public boolean isSymmetricI(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        queue.add(root);
        // 这里一定要使用isEmpty方法进行判断
        while (!queue.isEmpty()) {
            TreeNode treeNode1 = queue.poll();
            TreeNode treeNode2 = queue.poll();
            if (treeNode1 == null && treeNode2 == null) {
                continue;
            }
            if (treeNode1 == null || treeNode2 == null) {
                return false;
            }
            if (treeNode1.val != treeNode2.val) {
                return false;
            }
            queue.add(treeNode1.left);
            queue.add(treeNode2.right);
            queue.add(treeNode1.right);
            queue.add(treeNode2.left);
        }
        return true;
    }
}
